Twelve problems were presented to the jury of IOI.



Nine problems for the first day.

Three problems for the second day.







The IOI jury selected three problems for the first day:



 1. The necklace of beads. 

 2. The companies's shares. 

 3. Rectangles of different colours.



And one problem for the second day:



 1. The travel around Canada.





For further information 





FIRST DAY 



Problem 1.1.a: 



You have a necklace of n beads (n <100) some of which are red, others blue and others white, 



arranged at random. Let's see two examples for n = 29: 



1 2 1 2 



o x x o x o o x 



o x x x 



o o x o 



o o @ o 



x o @ @ 



x x o o 



x x x x 



x x o x 



o o x o 



x o o o 



x o o o 



o o o x 



o x o o o @ 



Figure a Figure b 



o red bead 



x blue bead 



@ white bead 



(The beads considered first and second in the text that follows have been marked in the picture). 



The configuration in Fig. a) may be represented as a string of b's and r's, where b represents a 



blue bead and r a red one, as follows: 



brbrrrbbbrrrrrbrrbbrbbbbrrrrb 



Suppose you are to break the necklace, lay it out straight, and then collect beads of the same 



colour from one end until you reach a bead of a different colour, and do the same for the other 



end (which may not be of the same colour as the beads collected before this). 



Determine the point where the necklace should be broken so that the most number of beads can 



be collected. 



For example, for the necklace in Fig. a), 8 beads can be collected, with the breaking point either 



between bead 9 and bead 10, or between bead 24 and bead 25. 



In some necklaces, white beads had been included as shown in Figure b) above. When 



collecting beads, a white bead that is encountered may be treated as either red or blue, and 



painted with the desired colour. The string that represents this configuration will include the 



symbols: r, b and w. 



Write a program to do the following: 



1. Read a configuration from an ASCII input file, NECKLACE.DAT, with each configuration on 



one line. Write this data into an ASCII output file, NECKLACE.SOL. An example of an 



input file would be: 



Example: 



NECKLACE.DAT 



brbrrrbbbrrrrrbrrbbrbbbbrrrrb 



bbwbrrrwbrbrrrrrb 



2. For each configuration, determine the maximum number, M, of beads collectable, along 



with a breaking point. 



3. Write to the outfile, NECKLACE.SOL, the number M and the breaking point. The solutions 



for different configurations should be separated with a blank record. 



Example of a possible solution: 



NECKLACE.SOL 



brbrrrbbbrrrrrbrrbbrbbbbrrrrb 



8 between 9 and 10 



bbwbrrrwbrbrrrrrb 



10 between 16 and 17 



Problem 1.2.a: 



The economic situation has turned bad. Due to a shortage of money in circulation and lack of 



credit, many factories have contracted debts that they cannot pay. There are, at most, 1000 



factories. 



All factories act as sellers (they sell their production) as well as buyers (they buy raw materials 



and component parts). So they contract debts among themselves. Finally, someone has had the 



idea of paying debts with ... debts. 



Say factory A owes $100 to factory B, factory B owes $50 to factory C, and C owes $75 to A. The 



sum of all the debts is $225. Factory A uses its credit with factory C to pay part of its debt to 



factory B. So, 



A to B $25 



B to C $50 



C to B $75 



This way, the total debt may be reduced to a minimal sum and the list of debts becomes: 



A to B $25 



C to B $25 



The problem is to write a program for paying debts with debts. 



1. Read a list of debts from an ASCII input file, DEBT.DAT, and write this data to an ASCII 



output file, DEBT.SOL. Each record in the list consists of three items: two factory codes 



and the amount owed by the first to the second. Different lists will be separated by a blank 



record as shown in the example below. 



Calculate and output to DEBT.SOL the total amount of debts. 



2. Reconstruct the list of debts so that the total amount of debts is minimal. Write to 



DEBT.SOL the new list of debts in the same form as the input list. 



3. Calculate and output to DEBT.SOL the total amount of debts in the new list. 



Example: 



DEBT.DAT 



A B 100.00 



B C 50.00 



C A 75.00 



A B 1500.00 



B C 1100.00 



D A 1400.00 



Example of a possible solution: 



DEBT.SOL 



A B 100.00 



B C 50.00 



C A 75.00 



Total = $225.00 



A B 25.00 



C B 25.00 



Total = $50.00 



A B 1500.00 



B C 1100.00 



D A 1400.00 



Total = $4000.00 



A B 100.00 



D B 300.00 



D C 1100.00 



Total = $1500.00 



Problem 1.3.a: 



In the city of Sinistra, the Town Council has forbidden right turns. In order to enforce this rule, all 



car drivers are required by the Town Council to install a computer in their vehicles. This computer 



records the vehicle coordinates every time the vehicle turns right or left. At the end of each trip, a 



sequence of positions is transmitted to a Council computer, which calculates the amount of the 



traffic ticket by charging a fine of $50 for each right turn. The problem to solve is: given the 



sequence of positions of a car, calculate the amount of the traffic ticket. 



Details: 



A trip is represented by a sequence of 2 or more points: p1, p2, ...., pN. Each point is a pair of 



numbers (i, j), where i and j are the coordinates of the position of the car in a coordinate system 



with origin at the Town Hall. 



p1 is the position where the trip began, pN is the position where it ended, and the other points 



are the corners where the car turned left or right. The streets are straight lines of arbitrary 



direction. 



The problem is to write a program to: 



1. Read from the input ASCII file, SINISTRA.DAT, and write in an output file, SINISTRA.SOL, 



the number N of points in the trip on one line and each point in the trip on the next N lines. 



Each data set will be separated from the next by a blank line. Each point in the input 



sequence is a pair of numbers separated by a blank with consecutive points on consecutive 



lines, appearing in the order p1, ..., pN. 



2. Compute the traffic ticket for the given trip. 



3. Write in the output ASCII file SINISTRA.SOL the amount of the traffic ticket that must be 



paid to the Town Council for each trip. Separate the amounts for the trips with a blank 



record. 



Example: 



SINISTRA.DAT 



3 



4 1 



5.5 4 



5 2 



4 



0 1 



-1 0 



0 -1 



1 0 



SINISTRA.SOL 



3 



4 1 



5.5 4 



5 2 



Traffic ticket: $50 



4 



0 1 



-1 0 



0 -1 



1 0 



Traffic ticket: $0 



Problem 1.1.b: 



The computer and a child are playing in the following way: 



The child thinks of a sequence of four colours (not necessarily different) chosen out of six possible 



colours. For convenience, let us use the numbers between 1 and 6 for denoting the six colours. 



The computer (your program) must find this sequence using the information it obtains from the 



child's answers. 



The computer displays a sequence on the screen and the child must answer, using the keyboard 



to enter the answers, the following two questions: 



a) How many colours are right but not in the right positions? 



b) How many right colours are in the right positions? 



Example: Suppose the child has chosen the sequence: 4655. One possible way to find this 



sequence may be: 



COMPUTER YOUR ANSWER 



1234 a) 1 b) 0 



5156 a) 2 b) 1 



6165 a) 1 b) 1 



5625 a) 1 b) 2 



5653 a) 1 b) 2 



4655 a) 0 b) 4 



Write a program that will always find the sequence chosen by the child in at most 6 steps. If you 



cannot do this, write a program to find the sequence chosen by the child in at most 10 steps. 



Problem 1.2.b: 



Some companies are partial owners of other companies because they have acquired part of their 



total shares. For example, Ford owns 12% of Mazda. It is said that a company A controls 



company B if, at least, one of the following conditions is satisfied: 



a) A = B 



b) A owns more than 50% of B 



c) A controls k (k > 1) companies, 



C(1), ..., C(k), so that: 



C(i) owns x(i)% of B for 1 < i < k and 



x(1) + .... + x(k) > 50. 



The problem to solve is: 



Given a list of triples (i,j,p) which means that the company i owns p% of company j, calculate all 



the pairs (h,s) so that company h controls company s. There are at most 100 companies. 



Write a program to: 



1 Read from an ASCII input file, COMPANY.DAT, the list of triples, (i,j,p), to be 



considered for each case (that is, each data set), where i, j and p are positive integers. 



Different cases (data sets) will be separated with a blank record. 



2 Find all the pairs (h,s) so that company h controls company s. 



3 Write to an ASCII output file, COMPANY.SOL, all the pairs (h,s) found, with h different 



from s. The pairs (h,s) must be written in consecutive records and in increasing order of 



h. The solutions for different cases must be separated with a blank record. 



Example: 



COMPANY.DAT 



2 3 25 



1 4 36 



4 5 63 



2 1 48 



3 4 30 



4 2 52 



5 3 30 



1 2 30 



2 3 52 



3 4 51 



4 5 70 



5 4 20 



4 3 20 



COMPANY.SOL 



4 2 



4 3 



4 5 



2 3 



2 4 



2 5 



3 4 



3 5 



4 5 



Problem 1.2.c: 



A sequence of positive integers 



a1,.... aN 



is called an additive chain of length N if for every k, 1 < k < N, there exists indices i and j, 



1< i < j < N, so that: 



ak = ai + aj 



For example: 



1 2 3 5 



1 2 3 4 5 



1 2 4 5 



are additive chains. 



The problem is, given a positive integer a, find an additive chain with minimal length N that has 



a1 = 1 and aN = a. 



Write a program to: 



1 Read from an ASCII input file, CHAIN.DAT the number a. Different cases will be separated 



with a blank record. 



2 Find an additive chain of minimal length which starts with 1 and ends with a. 



3 Write to an ASCII output file, CHAIN.SOL, the additive chain obtained. The solutions for 



different cases must be separated with a blank record. 



Example: 



CHAIN.DAT 



3 



5 



Example of a possible solution: 



CHAIN.SOL 



1 2 3 



1 2 3 5 



Problem 1.1.c: 



You are given a general chessboard of nxn squares, n < 10. White squares and black squares of 



the chessboard are arbitrarily arranged, but satisfy the following conditions: 



i) Each column contains at least one white square. 



ii) There is at least one column that contains only white squares. 



You are requested to place castles into squares of the chessboard so that: 



1) castles are only placed on white squares. 



2) on every row and every column there is at most one castle. 



3) each white square not containing a castle that is dominated by a castle on the same row 



must also be dominated by another castle on the same column. 



Write a program that does the following tasks: 



a. Read from an ASCII input file, CHESS.DAT, the number n and the configuration for an nxn 



chessboard, that is, n strings of 1's and 0's where 1 represents a white square and 0 



represents a black square. 



Write this data to an ASCII output file, CHESS.SOL. 



b. Place as many castles as possible on the squares of the chessboard so that the three 



above conditions are satisfied. 



c. Output to CHESS.SOL the total M of castles placed and the chessboard where the white 



squares have been replaced by the character "X" if you have placed a castle there. 



Example: 



CHESS.DAT 



3 



010 



110 



011 



4 



1111 



0001 



0001 



0001 



CHESS.SOL 



3 



010 



110 



011 



3 



0X0 



X10 



01X 



4 



1111 



0001 



0001 



0001 



1 



1111 



000X 



0001 



0001 



Problem 1.2.c: 



New Makeup Ltd. is an important factory which produces N different cosmetics. Every month, 



New Makeup sends a shipment to its branch in Mallorca. Each cosmetic has different price and 



volume. 



This week the longshoremen of Buenos Aires Port have announced they will go on strike starting 



next Monday. Nobody knows when port activities will be normalized. New Makeup's next 



shipment is on Saturday and, for economic reasons, the factory needs to maximize the 



shipment's value. 



You have to give an answer to New Makeup's General Manager. For this, different data sets have 



been written in an ASCII input file, MAKEUP.DAT. Each data set will look like this: 



N (the total number of different products) 



M (ship hold's capacity) 



P1 V1 (price and volume of each unit of product 1) 



P2 V2 (price and volume of each unit of product 2) 



......... 



PN VN (price and volume of each unit of product N) 



where the numbers N, M, Pi, Vi (1 < i < N) are positive integers. 



Write a program to: 



1. Read the next data set from MAKEUP.DAT. 



2. Determine how many units of each product have to be included in the shipment so that: 



* the shipment's volume doesn't exceed the ship hold's capacity 



* the shipment's value is maximum. 



3. Write into the ASCII output file, MAKEUP.SOL: 



* the quantity of units of each product included in the shipment 



* the shipment's value 



* the shipment's volume 



The solutions to different data sets must be separated by a blank record. 



Example: 



MAKEUP.DAT 



2 



6 



4 3 



7 4 



5 



20 



2 3 



3 4 



12 10 



17 11 



7 6 



MAKEUP.SOL 



Prod. 1 = 2 



Prod. 2 = 0 



Value = $8 



Volume = 6 



Prod. 1 = 1 



Prod. 2 = 0 



Prod. 3 = 0 



Prod. 4 = 1 



Prod. 5 = 1 



Value = $26 



Volume = 20 



Problem 1.3.c: 



N rectangles of different colours are superposed on a white sheet of paper. The sheet's sizes are: 



a cm wide and b cm long. The rectangles are put with their sides parallel to the sheet's borders. 



All rectangles fall within the borders of the sheet. As result, different figures of different colours 



will be seen. Two regions of the same colour are considered to be part of the same figure if they 



have at least one point in common; otherwise, they are considered different figures. The problem 



is to calculate the area of each of these figures. a, b are even positive integers not greater than 



30. 



The coordinate system considered has origin at the sheet's center and the axes parallel to the 



sheet's borders: 



Different data sets are written in an ASCII input file, RECTANG.DAT: 



a, b and N will be in the first line of each data set, separated by a blank space. 



* In each of the next N lines you will find: 



* the integer coordinates of the position where the left lower vertex of the rectangle was 



put. 



* followed by the integer coordinates of the position where the upper right vertex of the 



rectangle was put 



* and, then, the rectangle's colour represented by an integer between 1 and 64. White 



colour will be represented by 1. 



The order of the records corresponds to the order used to put the rectangles on the sheet. 



Different data sets will be separated with a blank record. 



Write a program to: 



1. Read the next data set from RECTANG.DAT 



2. Calculate the area of each coloured figure 



3. Write in an ASCII output file, RECTANG.SOL, the colour and the area of each coloured 



figure as shown in the example below. These records will be written in increasing order of 



colour. The solutions to different data sets will be separated by a blank record. 



Example: 



RECTANG.DAT 



20 12 5 



-7 -5 -3 -1 4 



-5 -3 5 3 2 



-4 -2 -2 2 4 



2 -2 3 -1 12 



3 1 7 5 1 



30 30 2 



0 0 5 14 2 



-10 -7 0 13 15 



RECTANG.SOL 



1 172 



2 47 



4 12 



4 8 



12 1 



1 630 



2 70 



15 200 



SECOND DAY 



Problem 2.1: 



You have won a contest organized by a Canadian airline. The prize is a free ticket to travel 



around Canada, beginning in the most western point visited by this airline, then traveling only 



from West to East until you reach the most eastern point visited by this airline, and then coming 



back only from East to West until you reach the starting point. No city may be visited more than 



once, except for the starting city, which must be visited exactly twice (at the beginning and the 



end of the trip). You are also not allowed to use any other airline or any other means of 



transportation. The problem to solve is: given a list of cities and a list of direct flights between 



pairs of cities, find out an itinerary which visits as many cities as possible satisfying the above 



conditions. 



Different data sets are written in an ASCII input file, C:\IOI\ITIN.DAT. Each data set consists of: 



* in the first line: the number N of cities visited by the airline and the number V of direct flights 



that will be listed. N will be a positive integer not larger than 100. V is any positive integer. 



* in each of the next N lines: a name of a city visited by the airline. The names are ordered 



from West to East in the input file. That is, the i-th city is East of the j-th city if and only if i > j 



(There aren't two cities in the same meridian). The name of each city is a string of, at most, 15 



digits and/or characters of the Latin alphabet, for example: 



AGR34 or BEL4 



* in each of the next V lines: two names of cities, taken from the list of cities, separated by a 



blank space. If the pair 



city1 city2 



appears in a line, it indicates that there exists a direct flight from city1 to city2 and also a direct 



flight from city2 to city1. 



Different data sets will be separated by an empty record (that is, a line containing only the end of 



line character). There will be no empty record after the last data set. The following example is 



stored in file C:\IOI\ITIN.DAT. 



8 9 



Vancouver 



Yellowknife 



Edmonton 



Calgary 



Winnipeg 



Toronto 



Montreal 



Halifax 



Vancouver Edmonton 



Vancouver Calgary 



Calgary Winnipeg 



Winnipeg Toronto 



Toronto Halifax 



Montreal Halifax 



Edmonton Montreal 



Edmonton Yellowknife 



Edmonton Calgary 



5 5 



C1 



C2 



C3 



C4 



C5 



C5 C4 



C2 C3 



C3 C1 



C4 C1 



C5 C2 



The input may be assumed correct and no checking is necessary. 



The solution found for each data set must be written to an ASCII output file, C:\IOI\ITIN.SOL: in 



the first line, the total number of cities in the input data set; in the next line, the number M of 



different cities visited in the itinerary, and in the next M+1 lines the names of the cities, one by 



line, in the order in which they will be visited. Note the first city visited must be the same as the 



last. If no solution is found for a data set, only two records for this data set must be written in 



ITIN.SOL, the first one giving the total number of cities, and the second one saying: "NO 



SOLUTION". A possible solution for the above example: 



ITIN.SOL 



8 



7 



Vancouver 



Edmonton 



Montreal 



Halifax 



Toronto 



Winnipeg 



Calgary 



Vancouver 



5 



NO SOLUTION 



Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for 



Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL. 



Problem 2.2: 



Once upon a time there was a gardener whose works were easy to recognize: he divided the 



garden in triangles and he planted flowers of the same colour in each of them. 



A millionaire called the gardener to design his garden so that: 



* each of the N beautiful fountains of his garden, numbered from 1 to N, had to be a vertex of 



at least one of the triangles. No fountain could be on the side of a triangle of which it was not a 



vertex. 



* a bee could fly in a straight line from any fountain to any other fountain flying continuously over 



flowers or fountains. 



* two adjacent triangles (those with a common side) always had to be planted with different 



colours. 



* once he had chosen the triangles, he had to use flowers of as few colours as possible. 



Write a program to solve the gardener's problem. 



Different data sets are written in an ASCII input file, C:\IOI\GARDEN.DAT. Each data set will look 



like this: 



N (the number of fountains) 



x1 y1 (coordinates of fountain 1) 



...... 



xN yN (coordinates of fountain N) 



where N, xi, yi , 1 < i < N < 100, are integers. Different data sets will be separated by an empty 



record (that is, a line containing only the end of line character). There will be no empty record after 



the last data set. 



The solution to each data set must be written in an ASCII output file, C:\IOI\GARDEN.SOL, as 



follows: 



N (the number of fountains in the input) 



m (the number of triangles drawn) 



p (the number of colours used) 



r1 s1 t1 C1 (r1,s1,t1 are the fountains at the vertices of triangle 1, and C1, a number 



between 1 and p, is the colour of triangle 1) 



.................... 



rm sm tm Cm (rm,sm,tm are the fountains at the vertices of triangle m and Cm, a number 



between 1 and p, is the colour of triangle m) 



The input may be assumed correct, no checking is necessary. 



The solutions to different data sets must be separated by an empty record. 



The following example is stored in file C:\IOI\GARDEN.DAT. 



7 



-2 2 



2 2 



-2 -2 



2 -2 



0 1 



1 0 



-1 0 



9 



-1 1 



0 1 



1 1 



-1 0 



0 0 



1 0 



-1 -1 



0 -1 



1 -1 



A possible solution appears below. 



7 



8 



3 



1 3 7 1 



1 7 5 2 



1 5 2 1 



2 5 6 2 



2 6 4 1 



4 6 3 2 



3 6 7 3 



7 5 6 1 



9 



8 



2 



5 1 2 2 



5 2 3 1 



5 3 6 2 



5 6 9 1 



5 9 8 2 



5 8 7 1 



5 7 4 2 



5 4 1 1 



Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for 



Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL. 



Problem 2.3: 



Imagine you are at a social get-together with at most 500 guests. The host invites you all to have 



dinner. There are several tables in the dining-room. The way the guests sit down at the tables is 



the following: each one sitting not alone at a certain table must know at least one person sitting 



at the same table and no one else sitting at other tables. 



It is supposed that if a person knows a second person, the second one knows the first person too. 



No one introduces himself to the other persons sitting in the same table. That means that if two 



persons are sitting at the same table, but initially they do not know each other, they do not know 



each other afterwards either. 



a) Determine how many tables are necessary and the persons sitting at each table. 



At each table there is only one person who will talk to the waiter, he is called the leader of the 



table. Each person relays his wishes concerning the menu to the persons he knows. The time 



allotted to each person to relay his wishes to each person he knows is supposed to be the same 



for each person. 



b) Find the most suitable person as leader of each table in order to receive information from all 



the persons sitting at the same table in the shortest possible period of time; produce at 



output the leader of each table. 



Afterwards, the host wishes to unify the tables. For this purpose, he calls some friends. Each of 



them, when coming, is introduced to the leaders of two tables, links the tables, sits down at the 



new formed table and becomes the leader of this table. 



c) What is the order of linking the tables in this way, so that at last all tables are unified into a 



single one and the conditions of point b) are satisfied? Specify the minimum necessary 



period of time for the leader to get information from all the other persons. 



After the complete linking, the friends of the host are leaving and the tables get their initial 



structure until the end of the dinner. 



When dinner is over, the persons start leaving the tables. 



d) Determine, for each table, the minimum number of persons and the order in which they are 



leaving the table, until the persons who are still at the table do not know each other. 



Different data sets will be separated by an empty record (that is, a line containing only the end of 



line character). There will be no empty record after the last data set. 



The following example is stored in file C:\IOI\MEETING.DAT. 



8 



1 2 



1 3 



2 4 



7 6 



4 3 



5 6 



7 



1 2 



1 3 



2 3 



4 5 



5 6 



6 7 



C:\IOI\MEETING.SOL 



Table 1: 1 2 3 4 



Table 2: 5 6 7 



Table 3: 8 



Leader table 1: 2 



Leader table 2: 6 



Leader table 3: 8 



6 8 New leader: 9 



2 9 New leader: 10 



Period of time: 3 



Persons leaving table 1: 2 3 



Persons leaving table 2: 6 



Persons leaving table 3: 



Table 1: 1 2 3 



Table 2: 4 5 6 7 



Leader table 1: 1 



Leader table 2: 5 



1 5 New leader: 8 



Period of time: 3 



Persons leaving table 1: 1 2 



Persons leaving table 2: 5 6 



Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for 



Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL. 







Amalia B. de Capatto

   e-mail: ab@berma.org.ar

   Home: Naon 3099

   (1430) Buenos Aires ARGENTINA

   TE: +54-1-5430274

